\documentclass{ctexart}
\bibliographystyle{IEEEtran}
\usepackage{url}
\usepackage{graphicx}
\usepackage{algorithm,algorithmic}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{tikz}
\pagestyle{plain}
\title{DoubleLinkedList的实现}
\author{张祺\\信息与计算科学 2101  3210104145}
\date{2022年12月8日}
\begin{document}
\maketitle
\section{各数据结构之间的关系}
\subsection{$ad_{lists}$和struct $ad_{list}$}
$ad_{lists}$为邻接表，其本质是以结构体$ad_{list}$的地址为元素存储的序列，通过结构体构建出一个单向链表，用以存储指定顶点的所有邻点。
\subsection{$ad_{lists}$和Vec}
Vec[i]即为顶点i的入度和出度和，其值等于$ad_{lists}$中的所有节点vertex值为i的总数和$ad_{lists}$[i]下所有节点数减2。
\subsection{$adj_{lists}$和Vec}
Vec[i]即为顶点i的入度和出度和，其值等于$adj_{lists}$第i行、第i列中值非零的元素总数。若Vec中某一位置的值为零，即表示该点不存在。

\section{设计思路}
要构建一张图最重要的是要存储顶点和边的信息，如果是有权图则还要加上权重。为了区分邻接表和邻接矩阵，临界表默认为无权图，而邻接矩阵根据用户的输入自行界定。设置序列Vec用以存放所有节点的入度和出度和，如果和为零，则该节点不存在。如果对节点的名字有要求，只需要外部构建一个对应表，后续输出时按照既定表即可。
\subsection{邻接表}
为了构建起邻接表，我们在用户输入指定格式的边信息后，创建一新的节点存放v的值，并接在$ad_{lists}$[u]后，如果该单链表中已存在节点vertex值为v则不在重复插入。删除临界表中的点v需要遍历每个顶点链表下的所有节点，将节点vertex值为v的统一删除，并且将顶点v后的链表删除。删除邻接表中的边只需要在顶点u的链表中找到节点vertex值为v的节点并删除。
\subsection{邻接矩阵}
接收到用户的边信息后，将二维矩阵$adj_{lists}$[u][v]的值修正为element即可，如果$adj_{lists}$[u][v]的值已经不为零，则不在修改。删除邻接矩阵中的点v需要将矩阵中的第v行、第v列的值都改为零，删除邻接矩阵中的边只需要将第u行第v个元素修改为零。

\begin{figure}[h]
  \centering
  \includegraphics[width = 0.75\linewidth]{moyang.jpg}
  \caption{class Graph}
\end{figure}

\section{测试说明}
\subsection{向空图中按用户所输入的边绘制以邻接矩阵为存储方式的有权图，然后重复输入一指定边，并最后把该边删除。}
\begin{figure}[h]
  \centering
  \includegraphics[width = 0.75\linewidth]{123.png}
  \caption{}
\end{figure}
\subsection{直接将二维矩阵导入图中，以邻接表存储无权图。}
\begin{figure}[h]
  \centering
  \includegraphics[width = 0.75\linewidth]{124.png}
  \caption{}
\end{figure}
\end{document}
